package com.acwing.partition9;

import java.io.*;

/**
 * @author `RKC`
 * @date 2021/12/2 9:36
 */
public class AC899编辑距离 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        String[] words = new String[n];
        for (int i = 0; i < n; i++) {
            words[i] = reader.readLine();
        }
        while (m-- > 0) {
            s = reader.readLine().split(" ");
            String p = s[0];
            int k = Integer.parseInt(s[1]), ans = 0;
            for (String word : words) {
                int res = dynamicProgramming(word, p);
                if (res <= k) ans++;
            }
            writer.write(ans + "\n");
        }
        writer.flush();
    }

    private static int dynamicProgramming(String s, String p) {
        int[][] dp = new int[s.length() + 1][p.length() + 1];
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                dp[i][j] = 0x3f3f3f3f;
            }
        }
        for (int i = 1; i <= s.length(); i++) dp[i][0] = i;
        for (int j = 1; j <= p.length(); j++) dp[0][j] = j;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
        return dp[s.length()][p.length()];
    }
}
